package P1370_上升下降字符串;

import java.util.*;

//上升下降字符串
public class Solution {
    public String sortString(String s) {
        SortedMap<Character,Integer> bullMap = new TreeMap<>();
        s.chars().forEach(value -> bullMap.put((char)value, bullMap.getOrDefault((char)value,0) + 1));
        StringBuilder sb = new StringBuilder(s.length());

        boolean up = true;
        boolean hasValue = false;
        SortedSet<Character> sortedSet = new TreeSet<>(bullMap.keySet());
        Character[] characters = sortedSet.toArray(new Character[0]);
        int index = 0;
        while(true) {
            while (index >= 0 && index < characters.length) {
                if (bullMap.getOrDefault(characters[index], 0) > 0) {
                    hasValue = true;
                    sb.append(characters[index]);
                    bullMap.put(characters[index], bullMap.get(characters[index]) - 1);
                }
                if(up){
                    index ++;
                }else{
                    index --;
                }
            }
            //每次循环完 检查各个桶是否需要删除无用的
            bullMap.entrySet().removeIf(entry -> entry.getValue() <= 0);
            sortedSet = new TreeSet<>(bullMap.keySet());
            characters = sortedSet.toArray(new Character[0]);

            if(!hasValue){
                break;
            }
            up = !up;
            hasValue = false;
            if(up){
                index = 0;
            }else{
                index = characters.length - 1;
            }
        }
        return sb.toString();


    }

    //上面的用各种utils类太麻烦了，直接用原生数组啊
    public String sortString2(String s){
        //用char数组比StringBuilder之类的快
        char[] ret = s.toCharArray();
        int[] arr = new int[26];
        //int可以直接用char来赋值，反之也行
        int aInt = 'a';
        //下面本来是:
        //        for(int i = 0;i<s.length();i++){
        //            arr[(int)s.charAt(i) - aInt] ++;
        //        }
        //但是每次charAt比先整体toCharArray然后取数组值要来的慢（应该。。）
        for(int i = 0;i<ret.length;i++){
            arr[ret[i] - aInt] ++;
        }
        boolean up = true,hasValue = false;
        int i;
        int index = 0;
        while(true) {
            i = up ? 0 : arr.length - 1;
            while (i >= 0 && i < arr.length) {
                if(arr[i] > 0){
                    hasValue = true;
                    ret[index++] = (char)(i + aInt);
                    arr[i] --;
                }
                if(up){
                    i++;
                }else{
                    i--;
                }
            }
            if(!hasValue){
                break;
            }
            up = !up;
            hasValue = false;
        }
        return new String(ret);
    }
    public static void main(String args[]){
        System.out.println(new P1370_上升下降字符串.Solution().sortString2("leetcode"));
    }
}
